package com.hardy.leetcode;

/**
 *合并两个排序的单链表
 * Created by 1340760685@qq.com on 2016/9/26.
 */
public class MergeTwoSortedLists {
    public static class ListNode{
        int val;
        ListNode next;
        public ListNode(int val){
            this.val=val;
        }
    }
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode newHead=new ListNode(0);
        ListNode p=newHead;
        ListNode p1=l1;
        ListNode p2=l2;
        while(p1!=null&&p2!=null){
            if(p1.val>p2.val){
                ListNode node=new ListNode(p2.val);
                p2=p2.next;
                p.next=node;
                p=node;
            }else{
                ListNode node=new ListNode(p1.val);
                p1=p1.next;
                p.next=node;
                p=node;
            }
        }
        if(p1!=null){
            p.next=p1;
        }
        if(p2!=null){
            p.next=p2;
        }
        return newHead.next;
    }

    public static void main(String[] args) {
        ListNode l1=new ListNode(1);
        l1.next=new ListNode(3);
        l1.next.next=new ListNode(5);
        l1.next.next.next=new ListNode(7);
        l1.next.next.next.next=new ListNode(9);
        ListNode l2=new ListNode(2);
        l2.next=new ListNode(4);
        l2.next.next=new ListNode(6);
        l2.next.next.next=new ListNode(8);
        l2.next.next.next.next=new ListNode(10);
        ListNode res=mergeTwoLists(l1,l2);
        ListNode p=res;
        while(p!=null){
            System.out.print(p.val+" ");
            p=p.next;
        }
    }
}
